首页 > 试题广场 >

判断一个链表是否为回文结构

[编程题]判断一个链表是否为回文结构
  • 热度指数：185087 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 ，链表中每个节点的值满足
示例1

输入

{1}

输出

true
示例2

输入

{2,1}

输出

false

说明

2->1
示例3

输入

{1,2,2,1}

输出

true

说明

1->2->2->1

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Python 3
杨枝甘露yyds头像 杨枝甘露yyds 
class Solution:
    def isPail(self , head: ListNode) -> bool:
        # write code here
        if not head: return False
        res = []
        while head:
            res.append(head.val) 
            head = head.next
        x = res[::-1]
        if res==x:
            return True
        else:
            return False
发表于 2022-07-26 01:20:27 回复(0)
Python 3
小大小菜鸡头像 小大小菜鸡
1. 找到中点，并把链表切成两段
2. 翻转后面一段
3. 依次比较数值 

class Solution:
    def isPail(self , head: ListNode) -> bool:
        if not head&nbs***bsp;not head.next:
            return True
        # write code here
        # 1.找到中点
        fast, slow = head, head
        slow_pre = head
        while fast and fast.next:
            fast = fast.next.next
            slow_pre = slow
            slow = slow.next
        # 2.slow 会在中间靠右的地方
        # [1, 2, 2, 1]    => slow 右边的 2
        # [1, 2, 3, 2, 1] => slow 在正中间
        # 断开链表
        slow_pre.next = None
        # 2.翻转链表
        def reverse(node):
            prev = None
            while node:
                tmp = node.next
                node.next = prev
                prev = node
                node = tmp
            return prev
        
        slow = reverse(slow)
        # 因为 head 会少一些
        while head:
            if slow.val != head.val:
                return False
            slow = slow.next
            head = head.next
        return True


发表于 2022-07-19 22:50:18 回复(0)
Python 3
风软一江山头像 风软一江山 
class Solution:
    def isPail(self , head: ListNode) -> bool:
        temp1 = []
        while head:
            temp1.append(head.val)
            head = head.next
        temp2 = temp1[::-1]
        return temp1 == temp2

发表于 2022-07-18 15:15:15 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    def reverse(self, head):
        pre = None
        cur = head
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

    def isPail(self , head: ListNode) -> bool:
        if not head:
            return True
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        slow = self.reverse(slow)
        fast = head
        while slow:
            if slow.val != fast.val:
                return False
            fast = fast.next
            slow = slow.next
        return True
发表于 2022-06-16 19:00:45 回复(0)
Python 3
yifan1997头像 yifan1997 
class Solution:
    def isPail(self , head: ListNode) -> bool:
        val=[]
        current_node=head
        while(current_node != None):
            val.append(current_node.val)
            current_node=current_node.next
        return val==val[::-1]

发表于 2022-05-20 14:30:06 回复(0)
Python 3
找offer的小胡头像 找offer的小胡
利用python列表的转置：
class Solution:
    def isPail(self , head: ListNode) -> bool:
        result =[]
        if not head.next:
            return True
        while head:
            result.append(head.val)
            head = head.next
        return result[::-1] ==result
发表于 2022-04-12 10:05:45 回复(0)
Python 3
lun__头像 lun__ 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self , head: ListNode) -> bool:
        # write code here 
        ## 空值 和 单值 均是 True 
        if not head&nbs***bsp;not head.next:
            return True
        
        l = []
        ll = []
        cur = head 
        
        while cur:
            l.append(cur.val)
#             ll.append(cur.val)
            cur = cur.next 
        
        ll = l[:]  ## 使用这个会快一些
        l.reverse()
        
        if ll == l:
            return True
        else:
            return False 

发表于 2022-04-08 19:51:09 回复(0)
Python 3
路痴喵头像 路痴喵 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self , head: ListNode) -> bool:
        # write code here
        if head == None:
            return True
        
        p = head
        tmp = []
        while p != None:
            tmp.append(p.val)
            p = p.next
        
        if tmp == tmp[::-1]:
            return True
        else:
            return False

发表于 2022-03-19 21:34:47 回复(0)
Python 3
付付吖头像 付付吖
l=[]
        while head:
            l.append(head.val)
            head=head.next
        if l==l[::-1]:
            return True
        return False
发表于 2022-03-14 19:54:43 回复(0)
Python 3
Virtual~头像 Virtual~
思路：
1. 找到中点
2. 中点到尾部翻转
2. 对比翻转后的链表和head 
class Solution:
    def isPail(self , head: ListNode) -> bool:
        # write code here
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        # 寻找中点
        if fast.next:
            mid = slow.next
        else:
            mid = slow
        
        # 从mid开始翻转链表
        last = None
        while mid:
            next = mid.next
            mid.next = last
            last = mid
            mid = next
        
        # 开始对比回文
        while last:
            if last.val != head.val:
                return False
            last = last.next
            head = head.next
        
        return True


发表于 2022-03-03 16:50:29 回复(0)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def isPail(self , head: ListNode) -> bool:
        low=head
        fast=head
        dummy=head
        res=[]
        while fast and fast.next:
            if fast.next.next:
                res.append(low.val)
                fast=fast.next.next
                low=low.next
            else:
                res.append(low.val)
                
                break
        low=low.next
        while low and low.next:
            if res.pop()==low.val:
                low=low.next
            else:
                return False
        return True

发表于 2022-01-04 09:01:09 回复(0)
Python 3
变秃才能变强头像 变秃才能变强 
class Solution:
    def isPail(self , head: ListNode) -> bool:
        # write code here
        pos= []
        neg = []
        while head:
            pos.append(head.val)
            head = head.next
        st = True
        for i in range(len(pos)//2):
            if pos[i] != pos[-i-1]:
                st = False
        return st
直接用堆栈[::-1]是会超时的，所以想办法优化这个的判断，其实只用看前一半就好，偶数长度，只用判断pos[x] 和pos[-x-1]是否相同，然后判断一般就好，奇数最中间那个不用管，剩下的类似
发表于 2021-11-26 01:08:42 回复(0)
Python 3
tangjunjun头像 tangjunjun 
class Solution:
    def isPail(self , head: ListNode) -> bool:
        # write code here
        a=[]
        if not head :return True
        p=head
        while p:
            a.append(p.val)
            p=p.next
        for i in range(len(a)):
            if a[i]!=a[-i-1]:
                return False
        return True


发表于 2021-11-17 23:42:35 回复(0)
Python 3
yusei_ooo头像 yusei_ooo 
# 栈＋双指针
class Solution:
    def isPail(self , head ):
        # write code here
        stack = [head.val]
        slow = head
        fast = head
        while(fast.next and fast.next.next):
            
            slow = slow.next
            fast = fast.next.next
            stack.append(slow.val)
            
        if fast.next is None:
            stack.pop()
        while(stack!=[] and slow.next):
            slow = slow.next
            if stack.pop()!=slow.val:
                return False
        return True

发表于 2021-09-21 11:15:55 回复(0)
Python 3
蒙太奇在秋天头像 蒙太奇在秋天
为什么没有人把链表转成数组再判断呢？ 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self , head ):
        # write code here
        valu = []
        while head:
            valu.append(head.val)
            head = head.next
        for i in range(len(valu)//2+1):
            if valu[i] != valu[len(valu)-1-i]:
                return 0
        return 1


发表于 2021-09-13 16:59:04 回复(0)
Python 3
牛客38477449号头像 牛客38477449号 
class Solution:
    def isPail(self , head ):
        # write code here
        if not head:
            return head
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        pre = None
        while slow:
            temp = slow.next
            slow.next = pre
            pre = slow
            slow = temp
        while head and pre:
            if head.val == pre.val:
                head = head.next
                pre = pre.next
            else:
                return False
        return True

发表于 2021-09-06 19:14:44 回复(0)
提交观点

问题信息

链表 双指针
难度：
23条回答 7540浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号